public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] coins = new int[]{1,2,5};
        System.out.println(test.change(5, coins));
    }

    public int change(int amount, int[] coins) {
        /**
         * 零钱兑换Ⅱ
         * 状态表示：
         *  dp[i][j]表示在前i个硬币中挑选，使得总金额等于j，此处所有最大硬币组合数
         * 状态转移方程：
         *
         * 初始化：
         *  dp[0][0] = 1;
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  dp[n][amount];
         * */
        // 1 预处理
        int n = coins.length;
        // 2 创建dp表
        int[][] dp = new int[n+1][amount+1];
        // 3 初始化
        for(int k = 0; k <= n; k++) {
            dp[k][0] = 1;
        }
        // 4 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= amount; j++) {
                // -不选
                dp[i][j] = dp[i-1][j];
                if(j >= coins[i-1]) {
                    dp[i][j] += Math.max(dp[i-1][j-coins[i-1]], dp[i][j - coins[i-1]]);
                }
            }
        }
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= amount; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        // 5 返回值
        return dp[n][amount];
    }
}
